package seqlist;

public class DoubleLinkedList {
    // 有效节点的个数
    private int size;
    // 当前头节点
    private DoubleNode head;
    // 当前尾节点
    private DoubleNode tail;

    public void addFirst(int val){
        // 首先创建一个新节点
//        DoubleNode node = new DoubleNode(val);
        // 这个新节点就是以后的头节点
        // 构造方法就是为对象属性进行初始化的！
        DoubleNode node = new DoubleNode(null,val,head);
        if (tail==null){
            tail=node;
        }
        else {
            head.prev=node;
        }
        head = node;
        size++;
    }
    public void addLast(int val){
        DoubleNode node=new DoubleNode(tail,val,null);
        if (tail==null){
            head=node;
        }else {
            tail.next=node;
        }
        tail=node;
        size++;
    }

    public void add(int index,int val){
        if (index<0||index>size){
            System.err.println("add index illegal!");
            return;
        }
        if (index==0){
            addFirst(val);
        }else if (index==size){
            addLast(val);
        }else {
            DoubleNode prev = node(index-1);
            DoubleNode next=prev.next;
            DoubleNode cur = new DoubleNode(prev,val,next);
            prev.next=cur;
            next.prev=cur;
            size++;
        }
    }



    public void removeIndex(int index){
        if (index<0||index>=size){
            System.err.println("remove index illegal!");
            return;
        }
        DoubleNode cur = node(index);
        unlink(cur);
    }

    /**
     * 删除出现第一个值为val的节点
     */
    public  void removeValueOnce(int val){
        for (DoubleNode x=head;x!=null;x=x.next){
            if(x.val==val){
                unlink(x);
                break;
            }
        }
    }

    public void removeAllValue(int val){
        for (DoubleNode x=head;x!=null;x=x.next){
            if (x.val==val){
                //x就是待删除的节点
                //暂存后继节点的位置
                DoubleNode successor = x.next;
                unlink(x);
                x=successor;
            }else {
                x=x.next;
            }
        }
    }

    /**
     * 删除当前双向链表中的node节点
     * @param node
     */
    private void unlink(DoubleNode node){
    //1.前空后空
    //2.前不空后空
    //3.前不空后不空
    //4.前空后不空
    DoubleNode prev = node.prev;
    DoubleNode successor = node.next;
    //先处理node前半部分
    if (prev==null){
        head=successor;
    }else {
        prev.next=successor;
        node.prev=null;
    }
    if (successor==null){
        tail = prev;
    }else {
        successor.prev=prev;
        node.next=null;
    }
    size--;
}

private DoubleNode node(int index){
        DoubleNode x=null;
        if (index<size/2){
            x=head;
            for (int i = 0; i < index; i++) {
                x=x.next;
            }
        }else {
            x=tail;
            for (int i = size-1; i >index ; i--) {
                x=x.prev;
            }
        }
        return x;
}

    public String toString() {
        String ret = "";
        for (DoubleNode x = head;x != null;x = x.next) {
            ret += x.val;
            ret += "->";
        }
        ret += "NULL";
        return ret;
    }
}
// 双向链表的节点类
class DoubleNode {
    // 前驱节点
    DoubleNode prev;
    // 当前节点值
    int val;
    // 后继节点
    DoubleNode next;
    // alt + insert

    public DoubleNode() {}

    public DoubleNode(int val) {
        this.val = val;
    }

    public DoubleNode(DoubleNode prev, int val, DoubleNode next) {
        this.prev = prev;
        this.val = val;
        this.next = next;
    }
}